/*
 * @lc app=leetcode.cn id=218 lang=java
 *
 * [218] 天际线问题
 */

// @lc code=start

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);

        List<Integer> boundaries = new ArrayList<>();
        
        for(int[] building : buildings) {
            boundaries.add(building[0]);
            boundaries.add(building[1]);
        }

        Collections.sort(boundaries);

        List<List<Integer>> res = new ArrayList<>();
        int n = buildings.length;
        int idx = 0;

        for(int boundary : boundaries) {
            while(idx < n && buildings[idx][0] <= boundary) {
                pq.offer(new int[]{buildings[idx][1], buildings[idx][2]});
                idx++;
            }

            while(!pq.isEmpty() && pq.peek()[0] <= boundary) {
                pq.poll();
            }

            int maxn = pq.isEmpty() ? 0 : pq.peek()[1];
            if(res.size() == 0 || maxn != res.get(res.size() - 1).get(1)) {
                List<Integer> tmp = new ArrayList<>();
                tmp.add(boundary);
                tmp.add(maxn);
                res.add(tmp);
            }
        }
        return res;
    }
}
// @lc code=end

